package Hot100;

import common.ListNode;
import common.TreeNode;

/**
 * @author zhangmin
 * @create 2021-12-29 13:28
 *
 * 双指针技巧：
 * 141. 环形链表---判断有无环
 * 142. 环形链表 II---找到环起点
 * 167. 两数之和 II - 输入有序数组
 * 19. 删除链表的倒数第 N 个结点
 * 876. 链表的中间结点
 * 344. 反转字符串
 *
 */
public class hasCycle141 {
    /**
     * 141. 环形链表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * 快慢指针，快指针每次走两步，慢指针每次走一步，两者相遇则有环
     * */
    public boolean hasCycle(ListNode head) {
        if(head==null) return false;
        ListNode fast=head,slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                return true;
            }
        }
        return false;
    }

    /**
     * 142. 环形链表 II
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 快慢指针，快指针走两步，慢指针走一步，等两者相遇，将慢指针移动到头，两者都一次一步，直到两者再相遇
     * */
    public ListNode detectCycle(ListNode head) {
        if (head==null) return null;
        ListNode slow=head,fast=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                break;
            }
        }
        if (fast==null||fast.next==null) return null;
        slow=head;
        while (slow!=fast){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }


    /**
     * 19. 删除链表的倒数第 N 个结点
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * 快指针先走n步，然后慢指针出发，当快指针到尾部时，快指针的位置就是倒数第n个节点
     * */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow=head,fast=head;
        while (fast!=null&&n>0){
            fast=fast.next;
            n--;
        }
        if (fast==null) {
            //head即为倒数第n个元素
            return head.next;
        }

        while (fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        slow.next=slow.next.next;
        return head;
    }

    /**
     * 876. 链表的中间结点
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
     * 快指针走两步，慢指针走一步，当快指针到尾部
     * */
    public ListNode middleNode(ListNode head) {
        ListNode fast=head,slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    /**
     * 167. 两数之和 II - 输入有序数组
     * 给定一个已按照 非递减顺序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
     * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。
     * 双指针，从两边向中间移动
     * */
    public int[] twoSum(int[] numbers, int target) {
        int left=0,right=numbers.length-1;
        while (left<right){
            int sum=numbers[left]+numbers[right];
            if (sum==target){
                return new int[]{left+1,right+1};
            }else if (sum<target){
                left++;
            }else {
                right--;
            }
        }
        return new int[]{-1,-1};
    }

    /**
     * 344. 反转字符串
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * 双指针
     * */
    public void reverseString(char[] s) {
        int left=0,right=s.length-1;
        while (left<right){
            char temp=s[left];
            s[left]=s[right];
            s[right]=temp;
            left++;right--;
        }
    }

}
